#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <upc.h>

//
// auxiliary functions
//
inline int max( int a, int b ) { return a > b ? a : b; }
inline int min( int a, int b ) { return a < b ? a : b; }

#define CHUNKING 64
#define CHUNKS 16
#define ROWSIZE CHUNKS*CHUNKING

 //  these two mulitply give 1024, if capacity is bigger than that, we're hosed. 
 //   If there are more than 16 threads, then threads these values need to be modified.
//  

double read_timer( )
{
    static int initialized = 0;
    static struct timeval start;
    struct timeval end;
    if( !initialized )
    {
        gettimeofday( &start, NULL );
        initialized = 1;
    }
    gettimeofday( &end, NULL );
    return (end.tv_sec - start.tv_sec) + 1.0e-6 * (end.tv_usec - start.tv_usec);
}

//
//  solvers
//
int build_table( int nitems, int cap, shared int *T, int *restrict w, int *restrict v )
{
  int wj, vj, i;
    
  wj = w[0];
  vj = v[0];
  upc_forall( int i = 0;  i <  wj;  i++; &T[i] ) T[i] = 0;
  upc_forall( int i = wj; i <= cap; i++; &T[i] ) T[i] = vj;
  upc_barrier;
  
  for( int j = 1; j < nitems; j++ )
    {
      wj = w[j];
      vj = v[j];
      upc_forall(i = 0;  i<=cap; i++; &T[i])
	{
	  if(i<wj)
	    T[i+ROWSIZE] = T[i];
	  else
	    T[i+ROWSIZE] =  max( T[i], T[i-wj]+vj );
	}
      //upc_forall( int i = 0;  i <  wj;  i++; &T[i] ) T[i+ROWSIZE] = T[i];
      //upc_forall( int i = wj; i <= cap; i++; &T[i] ) T[i+ROWSIZE] = max( T[i], T[i-wj]+vj );
      upc_barrier;
      
      T += ROWSIZE;
    }
  
  //printf("%d %d\n",cap, T[cap]);
  return T[cap];
}

void backtrack( int nitems, int cap, shared int *T, int *restrict w, int *restrict u )
{
  int i=0, j;
  
  if( MYTHREAD != 0 )
    return;
  
  //i = nitems*(cap+1) - 1;

  for(j=0; j<nitems-1; j++) i+=ROWSIZE;
  i+=cap;
  //printf("nitems %d ROWSIZE %d  i %d ", nitems, ROWSIZE, i);
  //printf("start %d %d\n",i,T[i]);
  for( j = nitems-1; j > 0; j-- )
    {
      u[j] = T[i] != T[i-ROWSIZE];
      i -= ROWSIZE + (u[j] ? w[j] : 0 );
    }
    u[0] = T[i] != 0;
}

//
//  serial solver to check correctness
//
int solve_serial( int nitems, int cap, int *w, int *v )
{
    int i, j, best, *allocated, *T, wj, vj;
    
    //alloc local resources
    T = allocated = malloc( nitems*(cap+1)*sizeof(int) );
    if( !allocated )
    {
        fprintf( stderr, "Failed to allocate memory" );
        upc_global_exit( -1 );
    }
    
    //build_table locally
    wj = w[0];
    vj = v[0];
    for( i = 0;  i <  wj;  i++ ) T[i] = 0;
    for( i = wj; i <= cap; i++ ) T[i] = vj;
    for( j = 1; j < nitems; j++ ) 
    {
        wj = w[j];
        vj = v[j];
        for( i = 0;  i <  wj;  i++ ) T[i+cap+1] = T[i];
        for( i = wj; i <= cap; i++ ) T[i+cap+1] = max( T[i], T[i-wj]+vj );
        T += cap+1;
    }
    best = T[cap];
    
    printf("%d %d\n",cap, T[cap]);
    //free resources
    free( allocated );
    
    return best;
}

//
//  benchmarking program
//
int main( int argc, char** argv )
{
  int i, j, best_value, best_value_serial, total_weight, nused, total_value;
    double seconds;
    shared int *weight;
    int* lweight;
    shared int *value;
    int* lvalue;
    int *used;

    
    //these constants have little effect on runtime
    int max_value  = 1000;
    int max_weight = 1000;
    
    //these set the problem size
    int capacity = 999;
    int nitems =  5000;

    shared int* total;   
    shared int* T;
    
    srand48( (unsigned int)time(NULL) + MYTHREAD );
    

    //allocate distributed arrays, use cyclic distribution
    weight = (shared int *) upc_all_alloc( nitems, sizeof(int) );
    value  = (shared int *) upc_all_alloc( nitems, sizeof(int) );
    lweight = (int *) malloc( nitems * sizeof(int) );
    lvalue  = (int *) malloc( nitems * sizeof(int) );
    used   = (int *) malloc( nitems * sizeof(int) );
    total  = (shared int *) upc_all_alloc( nitems * CHUNKS, CHUNKING*sizeof(int) );
    if( !weight || !value || !total || !used )
    {
        fprintf( stderr, "Failed to allocate memory" );
        upc_global_exit( -1 );
    }
    
    // init
    max_weight = min( max_weight, capacity );//don't generate items that don't fit into bag
    upc_forall( i = 0; i < nitems; i++; i )
    {
        weight[i] = 1 + (lrand48()%max_weight);
        value[i]  = 1 + (lrand48()%max_value);
    }
    
    // time the solution
    seconds = read_timer( );
    
    //  first, do one read from the global shared weight and value to a purely local copy.
    upc_barrier;  // need to have everyone finish their writing to weight and value.
    for(int i=0; i<nitems; i++)
      {
	lweight[i]=weight[i];
	lvalue[i] =value[i];
      }
 
    // now work with local lweight and lvalue instead of shared value.

    best_value = build_table( nitems, capacity, total, lweight, lvalue );

    backtrack( nitems, capacity, total, lweight, used );

    
    seconds = read_timer( ) - seconds;
    if(0)
      {
	printf("\n");
	for(i=0; i<nitems; i++) printf("%4d ",lweight[i]);
	printf("\n");
	for(i=0; i<nitems; i++) printf("%4d ",value[i]);

	printf("\n");
	for(i=0; i<nitems; i++) printf("%4d ",used[i]);

	T= total;
	for(j=0; j<nitems; j++)
	  {
	    printf("\n");
	    for(int i=0; i<=capacity; i++)
	      printf("%d ",T[i]);
	    T+=ROWSIZE;
	  }
	printf("\n");
      }

    // check the result
    if( MYTHREAD == 0 )
    {
        printf( "%d items, capacity: %d, time: %g\n", nitems, capacity, seconds );
        
        best_value_serial = solve_serial( nitems, capacity, lweight, lvalue );
        
        total_weight = nused = total_value = 0;
        for( i = 0; i < nitems; i++ )
            if( used[i] )
            {
                nused++;
                total_weight += weight[i];
                total_value += value[i];
            }
        
        printf( "%d items used, value %d, weight %d\n", nused, total_value, total_weight );
        
        if( best_value != best_value_serial || best_value != total_value || total_weight > capacity )
            printf( "WRONG SOLUTION\n" );
        
        //release resources
        upc_free( weight );
        upc_free( value );
        upc_free( total );


    }
    free( used );
    free(lweight);
    free(lvalue);    
    return 0;
}
